package bfs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class 课程表2 {
	//使用List<List<Integer>> 实现邻接表
	public int[] findOrder2(int n, int[][] p) {
        //1.准备邻接表
        List<List<Integer>> edges=new ArrayList<>();
        for(int i=0;i<n;i++){
            edges.add(new ArrayList<>());
        }
        int[] in=new int[n];
        //建图
        for(int i=0;i<p.length;i++){
            int a=p[i][0],b=p[i][1]; //b->a
            edges.get(b).add(a);
            in[a]++;
        }
        //拓扑排序
        Queue<Integer> q=new LinkedList<>();
        int[] ret=new int[n];
        int pos=0;
        //(1) 初始化
        for(int i=0;i<in.length;i++){
            if(in[i]==0){
                q.add(i);
            }
        }
        //(2)模拟
        while(!q.isEmpty()){
            int t=q.poll();
            ret[pos++]=t;
            for(int x:edges.get(t)){
                in[x]--;
                if(in[x]==0){
                    q.add(x);
                }
            }
        }

        //判断是否有环
        for(int i=0;i<in.length;i++){
            if(in[i]!=0){
                return new int[0];
            }
        }
        return ret;
    }
	
	
	
	//使用Map<Integer,List<Integer>>实现邻接表
	 public int[] findOrder1(int n, int[][] p) {
	        //1.准备相关结构
	        List<Integer> ret=new ArrayList<>();
	        int[] in=new int[n];  //入度数组
	        Map<Integer,List<Integer>> edges=new HashMap<>(); //顶点的邻边信息
	        //2.建图
	        for(int i=0;i<p.length;i++){
	            int a=p[i][0],b=p[i][1];
	            if(edges.containsKey(b)==false){
	                edges.put(b,new ArrayList<>());
	            }
	            edges.get(b).add(a);
	            in[a]++;
	        }
	        Queue<Integer> q=new LinkedList<>();
	        //bfs

	        //1.预处理
	        for(int i=0;i<n;i++){
	            if(in[i]==0){
	                q.add(i);
	            }
	        }
	        //2.bfs
	        while(!q.isEmpty()){
	            int t=q.poll();
	            ret.add(t);
	            for(int s:edges.getOrDefault(t,new ArrayList<>())){
	                in[s]--;
	                if(in[s]==0){
	                    q.add(s);
	                }
	            }
	        }

	        //判断是否有环
	        for(int x:in){
	            if(x!=0){
	                return new int[0];
	            }
	        }
	        //收集结果
	        int[] ans=new int[ret.size()];
	        for(int i=0;i<ret.size();i++){
	            ans[i]=ret.get(i);
	        }
	        return ans;
	    }
}
